题目分析

这个题目第一眼看上去，很面熟，但是又想不起来在哪里见到过。在翻看题解之后，发现这个题目和之前的背包问题非常相似，类似于一个二维的背包问题。下面我将题目进行转化，给你一个背包，背包的宽度和高度为m和n，其中宝物数组为strs，每个宝物也有宽度和高度两个属性，问最多能够装入多少个宝物？现在小伙伴们尝试一下能否独立求解出本题呢？

动态规划

背包问题的经典解法是动态规划，在0-1背包中，一维问题，创建一个二维数组dp[k][n]，其中k为宝物的个数，n为空间的大小。dp[i][j]代表遍历底i个物体时，当使用j个空间时能装入的物品个数。
$$\begin{cases} dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + 1) & j \ge w[i] \ dp[i - 1][j] & j < w[i] \end{cases}$$

在本题二维问题中，创建一个三位数组dp[k][m][n]，其中k为字符串个数，m为0的个数，n为1的个数。dp[k][i][j]代表遍历底k个字符串时，共有i个0，j个1时子集中包含字符串的最大个数。
$$\begin{cases} dp[k][i][j] = max(dp[k - 1][i][j], dp[k - 1][i - mm[k]][j - nn[k]] + 1) & i \ge mm[k] && j \ge nn[k] \ dp[k - 1][i][j] & else \end{cases}$$

算法的时间复杂度为$O(mnk)$，空间复杂度为$O(mnk)$

在0-1背包中，因为dp[i]仅与dp[i - 1]的状态有关，因此在一维问题中，可以使用一维数组记录状态，为了第i层的状态变化不影响上一层，可以使用倒序遍历实现。如果使用顺序遍历，dp[j] = dp[j - w[i]]会更新dp[j]的值，当使用dp[j]的值时，就不是更新前的值了，因此顺序遍历是不正确的，而逆序遍历，每次先更新后面的值，可以保证以后不会使用到。同理二维问题类似，可以进一步将时间复杂都缩小为$O(mn)$

下面是Python语言的题解

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for s in strs:
            mm = s.count('0')
            nn = len(s) - mm
            for i in range(m, mm - 1, -1):
                for j in range(n, nn - 1, -1):
                    dp[i][j] = max(dp[i - mm][j - nn] + 1, dp[i][j])
        return dp[-1][-1]

下面是Kotlin语言的题解

class Solution {
    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
        val dp = Array(m + 1){IntArray(n + 1)}
        for (str in strs) {
            val mm = str.count{it == '0'}
            val nn = str.length - mm
            for (i in m downTo mm) {
                for (j in n downTo nn) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - mm][j - nn] + 1)
                }
            }
        }
        return dp[m][n];
    }
}

对比Python和Kotlin两种语言，可以发现在创建多维数组时，相对于C++或Java语言较为麻烦，在字符串操作时，Python的内置函数较为方便，Kotlin语言需要使用lambda表达式。而且在倒序时，Python和正序类似，只用修改倒序的步长，Kotlin需要使用downTo语句。可以看出来Kotlin更像一种Java和Python的结合体，在变量声明和每行代码结尾不用分号，更类似于Python，而循环，选择结构中的大括号，以及代码的逻辑结构上更类似于Java。

刷题总结

这个题目难度适中，如果能够联想到背包问题，相信对于小伙伴们来说是不难的，如果联想不到，暴力法或者回溯法可能无法求解本题。